【算法导论】红黑树

​ 在了解红黑树之前，我们必须先了解二叉搜索树（又称二叉排序树，我在上一篇文章中有介绍），因为红黑树是一种特殊的二叉排序树：在每个节点上增加一个存储位来表示节点的颜色，因此红黑树共有五个域：color,key,lchild,rchild,p。

​ 红黑树的提出：一个高度为h的二叉排序树可以实现任何一种基本的动态集合操作:插入、删除、查找等操作，但是当树才高度比较高时，二叉树就会退化成链表。而红黑树能确保在最坏的情况下，基本的动态集合操作的时间为$O(logn)$.

红黑树的性质决定了红黑树的性能，红黑树共有五大性质：

1、 每个节点不是红的，就是黑的。

2、 根节点是黑的。

3、 每个叶节点都是黑的。

4、 若一个节点是红的，则他的子节点都是黑的。

5、 对于每个节点，从该节点出发到其子孙叶节点的所有路径上包含相同数目的黑节点。

图片的信息比笔述更加清新明了，下图1-3就是一棵红黑树的几种形式：

上图中，为了便于处理边界问题，我们采用一个哨兵来代表NIL。哨兵NIL是一个与普通节点有相同域的对象。它的color域为BLACK，其它域可随意设置。我在程序中将p、lchild、rchild设置为NULL，将key设置为-1.将所有指向NIL的指针都指向哨兵NIL。

下面先说明两个概念:内节点和外节点

内节点：把带关键字的节点称为内节点。

外节点：把没有子节点或父节点的节点称为外节点，我们把外节点都看成是哨兵NIL。

由于我们关注的是关键字key,因此我们主要关心内节点，所以在画红黑树的时候，常常忽略叶子，如上图3所示。

在介绍红黑树的插入和删除前，我们先必须介绍旋转这个概念。因为它在红黑树的插入、删除中，要用到很多。

旋转：分为左旋、右旋，它能够保持二叉排序树性质的局部操作。至于为什么能够保持性质，我也没有深入研究。前人不知道怎么发现这个操作。

我始终认为图像更能直观的表达更准确丰富的含义，我相信大家通过下图即可以明白左旋和右旋了。

如果对上图4还是不太明了，也没关系，具体举例能使你有更深刻的认识，下图5是在x上左旋的过程：

下面附上左旋和右旋的代码：

左旋和右旋的源代码：

/*************************************************\
函数功能：左旋
输入：    根节点、要左旋的节点、哨兵
输出：    根节点
\*************************************************/
RBTree* Left_Rotate(RBTree* root,RBTree* x,RBTree* NIL)
{
    RBTree* y=NULL;
    y=x->rchild;
    x->rchild=y->lchild;
    
    if(y->lchild!=NIL)
        y->lchild->p=x;
    y->p=x->p;
    
    if(y->p==NIL)
       root=y;
    else if(x==x->p->lchild)
        x->p->lchild=y;
    else
        x->p->rchild=y;
    y->lchild=x;
    x->p=y;
    return root;
}


/*************************************************\
函数功能：在节点z上右旋
输入：    根节点、要右旋的节点、哨兵
输出：    根节点
\*************************************************/
RBTree* Right_Rotate(RBTree* root,RBTree* x,RBTree* NIL)
{
    RBTree* y=NULL;
    y=x->lchild;
    x->lchild=y->rchild;
    if(y->rchild!=NIL)
        y->rchild->p=x;
    y->p=x->p;
    if(y->p==NIL)
       root=y;
    else if(x==x->p->lchild)
        x->p->lchild=y;
    else
        x->p->rchild=y;
    y->rchild=x;
    x->p=y;
    return root;
}

---

插入操作：插入函数和插入修正函数

​ 在前一篇文章中我已经介绍了二叉排序树，其中也有插入和删除操作。因为红黑树也是二叉排序树，因此其插入操作大同小异，不同之处在于，红黑树的性质会被插入和删除操作所破坏，因此就需要修正。修正包括两个操作：重新着色、旋转。

从上面的分析可知，红黑树的插入操作分为两步，首先像二叉排序树一样进行插入操作，然后调用修正函数来保持红黑树的性质。在插入操作中，我们都设置插入节点的color域为红而不是黑（如果是黑的话，性质4就不会破坏），为什么？请读者好好思考。下面为插入函数的实现：

插入函数源代码：

/*************************************************\
函数功能：插入一个节点z
输入：    根节点、插入的节点、哨兵
输出：    根节点
\*************************************************/
RBTree* Insert(RBTree* root,RBTree* z,RBTree* NIL)
{
//    printf("ok ");
    RBTree* leaf=NIL;
    RBTree* p=root;//指向根节点
    while(p!=NIL)//根节点不为空
    {
        //printf("dd");
        leaf=p;    //指向父节点
        if(z->key<p->key)
            p=p->lchild;
        else
            p=p->rchild;
    }

    z->p=leaf; //z为y的孩子节点 y=leaf
    if(leaf==NIL) //根节点为空
        root=z;
    else if(z->key<leaf->key)
        leaf->lchild=z;
    else
        leaf->rchild=z;
    
//    printf("%d ",root->key);
    

//    printf("%d ",root->color);
    return root;
}

​ 在Insert_FixUp插入修正函数中，循环截止条件为 z->p是黑色。如果z->p是红色，显然这就违返了红黑的树性质4。在循环中，我们要讨论6种情况，但是其中三种与另外三种是相互对称的，它可以由插入节点的父节点为祖父节点的左孩子还是右孩子来区分。下面我只讨论插入节点的父节点为祖父节点的左孩子的情况。在每一次迭代中，我们可能遇到以下三种情况。

• 情况一：叔叔是红色的
  这时只要把插入节点z的父亲z->p和uncle都设成黑色，并把祖父z->p->p设成红色。这样仍然确保了每一条路径上的黑色节点数不变。然后把z指向z->p->p，并开始新一轮的迭代。如下图6：

  

• 情况二：叔叔是黑色的情况下，插入节点为右孩子
  这时我们只要把z指向z->p，然后做一次Left-Rotate(z)。就可以把情况转化成情况三。

• 情况三：叔叔是黑色的情况下，插入节点为左孩子
  只要把z->p设成黑色，把z->p->p设成红色，然后就调用 Right_Rotate(z->p->p)，整棵树就修正了。情况二和情况三如下图：
  

插入修正函数的具体实现如下：

插入修正函数源代码：

/*************************************************\
函数功能：插入修正来维持红黑树的性质
输入：    根节点、插入的节点、哨兵
输出：    根节点
\*************************************************/
RBTree* Insert_FixUp(RBTree* root,RBTree* z,RBTree* NIL)
{
    RBTree* y=z;
    while(y->p->color==RED)//循环截止条件为父节点为黑
    {
        
        if(y->p==y->p->p->lchild)//插入节点的父节点为祖父节点的左孩子
        {
            RBTree* pr=y->p->p->rchild;
            if(pr->color==RED)//情况一：叔叔是红色的
            {
                y->p->color=BLACK;
                pr->color=BLACK;
                y->p->p->color=RED;
                y=y->p->p;
            }
            else //叔叔是黑色的，分两种情况
            {
                if(y==y->p->rchild)//情况二：叔叔是黑色的情况下，插入节点为右孩子
                {
                    y=y->p;
                    root=Left_Rotate(root,y,NIL);//情况二可以通过左旋变成情况三
                }
                y->p->color=BLACK;//情况三：叔叔是黑色的情况下，插入节点为左孩子
                y->p->p->color=RED;
                root=Right_Rotate(root,y->p->p,NIL);
            }
        }
        
        else//插入节点的父节点为祖父节点的左孩子,下面的情况与上面类似
            {
            RBTree* pl=y->p->p->lchild;
            if(pl->color==RED)
            {
                y->p->color=BLACK;
                pl->color=BLACK;
                y->p->p->color=RED;
                y=y->p->p;
            }
            else 
            {
                if(y==y->p->lchild)
                {
                    y=y->p;
                    root=Left_Rotate(root,y,NIL);
                }
                y->p->color=BLACK;
                y->p->p->color=RED;
                root=Left_Rotate(root,y->p->p,NIL);
            }
        }

    }

    root->color=BLACK;
    return root;
}

---

删除操作：删除函数和删除修正函数

​ 删除操作和插入操作一样，都可以和二叉排序树一样进行对比。红黑树的删除操作分为两步，首先像二叉排序树一样进行删除操作，然后调用修正函数来保持红黑树的性质。前一篇二叉排序树的文章也讲过，删除操作要比插入操作复杂一些，红黑树也不例外。删除函数的具体实现如下：

删除函数源代码：

/*************************************************\
函数功能：删除一个节点z
输入：    根节点、要删除的节点、哨兵
输出：    根节点
\*************************************************/
 RBTree* Delete(RBTree* root,RBTree* node,RBTree* NIL) 
 {
        RBTree* toDel = node;
        if (node->lchild != NIL && node->rchild != NIL) 
        {
            toDel = TreeNext(node,NIL);
        }

        RBTree* temp = toDel;
        while (temp->p != NIL)
        {
            
            temp = temp->p;
        }

        RBTree* replace = (toDel->lchild != NIL)? toDel->lchild: toDel->rchild;
        replace->p = toDel->p;
        if (replace->p == NIL) 
        {
            root = replace;
        }
        else if (toDel == toDel->p->lchild) 
        {
            replace->p->lchild = replace;
        }
        else 
        {
            replace->p->rchild = replace;
        }
        if (toDel != node) 
        {
            node->key = toDel->key;
        }
        if (toDel->color == BLACK)
        {
            //修改树，以保持平衡。
            root=Del_FixUp(root,replace,NIL);
        }
        delete toDel;
        return root;
    }<span style="font-family: Calibri, sans-serif;"><span style="font-size: 19px;">
</span></span>

​ 在Del_FixUp删除操作修正函数中，循环截止条件为z->color== RED。如果z->p是黑色，即删除的节点为黑色，显然这就违返了红黑的树性质5。在循环中，我们要讨论8种情况，但是其中4种与另外4种是相互对称的，它可以由删除的节点为父节点的左孩子还是右孩子来区分。下面我只讨论删除的节点为父节点的左孩子的情况:
在每一次迭代中，我们可能遇到以下4种情况：

• 情况一：兄弟为红色
  这时我们根据红黑树的性质可以肯定删除的节点x->p是黑色、其兄弟节点w->lchild是黑色。我们把x->pt与brother的颜色互换，然后做一次Left-Rotate(x->p)。做完之后x的新的兄弟：原w->lchild，是黑色的。因此我们在不破坏红黑树性质的前提下，把情况一转换成了情况二、情况三、情况四中的一个，如下图8：
  

• 情况二：兄弟为黑色，其两个孩子为黑色
  这时我们只要把w设成红色,然后把x移到x->p，这一次操作不会破坏红黑树的性质。如下图9（图中节点B不一定是红色，也可能是黑色）：

  

• 情况三：兄弟为黑色，且其左孩子为红色，右孩子为黑色
  我们把w与w->lchild的颜色互换，然后做Right-Rotate(w)。这样做不会破坏红黑树的性质。这时x的新的兄弟就是原w->lchild。而情况3被转化成了情况4,如图10：

  

• 情况四：兄弟为黑色，且其右孩子为红色
  先把w与x->parent的颜色互换，再做Left-Rotate(x->parent)。这时图中节点E（也就是原w->rchild）所在的路径就肯定少了一个黑色，而x所在的路径则多了一个黑色。那么我们就把使E也为黑色，这样就保持了红黑树的性质。如下图11：

具体的代码实现如下：

完整源代码：

#include<stdio.h>
#include<malloc.h>

enum Color{RED,BLACK};

typedef struct node//红黑树的节点结构
{
    enum Color color;
    struct node *p,*lchild,*rchild;
    int key;
}RBTree;

RBTree* Insert(RBTree* root,RBTree* z,RBTree* NIL);//插入
RBTree* Insert_FixUp(RBTree* root,RBTree* z,RBTree* NIL);//插入修正
RBTree* Left_Rotate(RBTree* root,RBTree* x,RBTree* NIL);//左旋
RBTree* Right_Rotate(RBTree* root,RBTree* x,RBTree* NIL);//右旋
RBTree* Delete(RBTree* root,RBTree* node,RBTree* NIL);//删除
void Layer(RBTree *p,int n);//广度优先遍历，用于查看红黑树的节点
RBTree* TreeNext(RBTree* node,RBTree* NIL);// 查找后继
RBTree* TreePre(RBTree* node,RBTree* NIL);// 查找前趋
RBTree* TreeMax(RBTree* root,RBTree* NIL);// 查找最大值
RBTree* TreeMin(RBTree* root,RBTree* NIL);// 查找最小值
RBTree* Del_FixUp(RBTree* root,RBTree* delNode,RBTree* NIL);//删除修正

void main()
{
    int arrayA[]={11,2,14,1,7,15,5,8,4};
    int n=sizeof(arrayA)/sizeof(int);
//    printf("%d\n",BLACK);

    RBTree* NIL=(RBTree*)malloc(sizeof(RBTree));//哨兵节点即外节点
    NIL->color=BLACK;
    NIL->key=-1;
    NIL->lchild=NIL->rchild=NULL;
    NIL->p=NULL;
    RBTree *root=NULL;//根节点
    root=NIL;
    for(int i=0;i<n;i++)
    {
        RBTree* z=(RBTree*)malloc(sizeof(RBTree));
        z->color=RED;
        z->key=arrayA[i];
        z->lchild=NIL;
        z->rchild=NIL;
        z->p=NIL;
        printf("\n插入节点的关键值为%d ",z->key);    
        root=Insert(root,z,NIL);    
        printf("\n插入修正前的广度遍历:\n");
        Layer(root,n);
        root=Insert_FixUp(root,z,NIL);
    //    printf("%d\n",i);
        printf("插入修正后的广度遍历:\n");
        Layer(root,n);
        printf("\n");
        
    }
    printf("插入操作完成！！\n\n");
    printf("删除节点的关键值为%d\n ",root->lchild->rchild->key);
    printf("\n删除顶节点后的广度遍历：\n");
    root=Delete(root,root->lchild->rchild,NIL);
    n=n-1;//删除一个节点 n减一
    Layer(root,n);

    }


/*************************************************\
函数功能：插入一个节点z
输入：    根节点、插入的节点、哨兵
输出：    根节点
\*************************************************/
RBTree* Insert(RBTree* root,RBTree* z,RBTree* NIL)
{
//    printf("ok ");
    RBTree* leaf=NIL;
    RBTree* p=root;//指向根节点
    while(p!=NIL)//根节点不为空
    {
        //printf("dd");
        leaf=p;    //指向父节点
        if(z->key<p->key)
            p=p->lchild;
        else
            p=p->rchild;
    }

    z->p=leaf; //z为y的孩子节点 y=leaf
    if(leaf==NIL) //根节点为空
        root=z;
    else if(z->key<leaf->key)
        leaf->lchild=z;
    else
        leaf->rchild=z;
    
//    printf("%d ",root->key);
    

//    printf("%d ",root->color);
    return root;
}

/*************************************************\
函数功能：插入修正来维持红黑树的性质
输入：    根节点、插入的节点、哨兵
输出：    根节点
\*************************************************/
RBTree* Insert_FixUp(RBTree* root,RBTree* z,RBTree* NIL)
{
    RBTree* y=z;
    while(y->p->color==RED)//循环截止条件为父节点为黑
    {
        
        if(y->p==y->p->p->lchild)//插入节点的父节点为祖父节点的左孩子
        {
            RBTree* pr=y->p->p->rchild;
            if(pr->color==RED)//情况一：叔叔是红色的
            {
                y->p->color=BLACK;
                pr->color=BLACK;
                y->p->p->color=RED;
                y=y->p->p;
            }
            else //叔叔是黑色的，分两种情况
            {
                if(y==y->p->rchild)//情况二：叔叔是黑色的情况下，插入节点为右孩子
                {
                    y=y->p;
                    root=Left_Rotate(root,y,NIL);//情况二可以通过左旋变成情况三
                }
                y->p->color=BLACK;//情况三：叔叔是黑色的情况下，插入节点为左孩子
                y->p->p->color=RED;
                root=Right_Rotate(root,y->p->p,NIL);
            }
        }
        
        else//插入节点的父节点为祖父节点的左孩子,下面的情况与上面类似
            {
            RBTree* pl=y->p->p->lchild;
            if(pl->color==RED)
            {
                y->p->color=BLACK;
                pl->color=BLACK;
                y->p->p->color=RED;
                y=y->p->p;
            }
            else 
            {
                if(y==y->p->lchild)
                {
                    y=y->p;
                    root=Left_Rotate(root,y,NIL);
                }
                y->p->color=BLACK;
                y->p->p->color=RED;
                root=Left_Rotate(root,y->p->p,NIL);
            }
        }

    }

    root->color=BLACK;
    return root;
}

/*************************************************\
函数功能：左旋
输入：    根节点、要左旋的节点、哨兵
输出：    根节点
\*************************************************/
RBTree* Left_Rotate(RBTree* root,RBTree* x,RBTree* NIL)
{
    RBTree* y=NULL;
    y=x->rchild;
    x->rchild=y->lchild;
    
    if(y->lchild!=NIL)
        y->lchild->p=x;
    y->p=x->p;
    
    if(y->p==NIL)
       root=y;
    else if(x==x->p->lchild)
        x->p->lchild=y;
    else
        x->p->rchild=y;
    y->lchild=x;
    x->p=y;
    return root;
}


/*************************************************\
函数功能：在节点z上右旋
输入：    根节点、要右旋的节点、哨兵
输出：    根节点
\*************************************************/
RBTree* Right_Rotate(RBTree* root,RBTree* x,RBTree* NIL)
{
    RBTree* y=NULL;
    y=x->lchild;
    x->lchild=y->rchild;
    if(y->rchild!=NIL)
        y->rchild->p=x;
    y->p=x->p;
    if(y->p==NIL)
       root=y;
    else if(x==x->p->lchild)
        x->p->lchild=y;
    else
        x->p->rchild=y;
    y->rchild=x;
    x->p=y;
    return root;
}


/*************************************************\
函数功能：删除一个节点z
输入：    根节点、要删除的节点、哨兵
输出：    根节点
\*************************************************/
 RBTree* Delete(RBTree* root,RBTree* node,RBTree* NIL) 
 {
        RBTree* toDel = node;
        if (node->lchild != NIL && node->rchild != NIL) 
        {
            toDel = TreeNext(node,NIL);
        }

        RBTree* temp = toDel;
        while (temp->p != NIL)
        {
            
            temp = temp->p;
        }

        RBTree* replace = (toDel->lchild != NIL)? toDel->lchild: toDel->rchild;
        replace->p = toDel->p;
        if (replace->p == NIL) 
        {
            root = replace;
        }
        else if (toDel == toDel->p->lchild) 
        {
            replace->p->lchild = replace;
        }
        else 
        {
            replace->p->rchild = replace;
        }
        if (toDel != node) 
        {
            node->key = toDel->key;
        }
        if (toDel->color == BLACK)
        {
            //修改树，以保持平衡。
            root=Del_FixUp(root,replace,NIL);
        }
        delete toDel;
        return root;
    }


/*************************************************\
函数功能：删除修正 维持红黑树的性质
输入：    根节点、要删除的节点、哨兵
输出：    根节点
\*************************************************/
   RBTree* Del_FixUp(RBTree* root,RBTree* delNode,RBTree* NIL)
   {
        RBTree* p = delNode;
        while (p != root && p->color == BLACK)
        {
            if (p == p->p->lchild)//要删除的节点为父节点的左孩子
            {
                RBTree* brother = p->p->rchild;
                if (brother->color == RED) //情况一：兄弟为红色
                {
                    brother->color = BLACK;
                    p->p->color = RED;
                    root=Left_Rotate(root,p->p,NIL);//经过旋转后 兄弟变为黑色，进入下面三种情况之一
                    brother = p->p->rchild;
                }
                if (brother->lchild->color == BLACK&& brother->rchild->color == BLACK)//情况二：兄弟为黑色，其两个孩子为黑色
                {
                    brother->color = RED;
                    p = p->p;
                }
                else 
                {
                    if (brother->rchild->color == BLACK)//情况三：兄弟为黑色，且其左孩子为红色，右孩子为黑色
                    {
                        brother->lchild->color = BLACK;
                        brother->color = RED;
                        root=Right_Rotate(root,brother,NIL);//转变为情况四
                        brother  = brother->p;
                    }
                    brother->color = brother->p->color;//情况四：兄弟为黑色，且其右孩子为红色
                    brother->p->color = BLACK;
                    brother->rchild->color = BLACK;
                    root=Left_Rotate(root,brother->p,NIL);
                    p = root;
                }
            }
            else//删除的节点为父节点的右孩子,下面的情况与上面类似
            {
                RBTree* brother = p->p->lchild;
                if (brother->color == RED) 
                {
                    brother->color = BLACK;
                    p->p->color = RED;
                    root=Right_Rotate(root,p->p,NIL);
                    brother = p->p->lchild;
                }
                if (brother->lchild->color == BLACK&& brother->rchild->color == BLACK)
                {
                    brother->color = RED;
                    p = p->p;
                }
                else 
                {
                    if (brother->lchild->color == BLACK) 
                    {
                        brother->rchild->color = BLACK;
                        brother->color = RED;
                        root=Left_Rotate(root,brother,NIL);
                        brother = brother->p;
                    }
                    brother->color = brother->p->color;
                    brother->p->color = BLACK;
                    brother->lchild->color = BLACK;
                    root=Right_Rotate(root,brother->p,NIL);
                    p = root;
                }
            }
        }
        p->color = BLACK;
        return root;
    }

   /*************************************************\
函数功能：广度优先遍历
输入：    根节点、节点数
输出：    无
\*************************************************/
void Layer(RBTree *p,int n)
{
    RBTree* queue[40];//queue数组用于存储节点地址
    int count=0;
    RBTree* s;
    int rear=0;  //队列尾指针
    int front=0; //队列头指针

    if(p!=NULL)//输入的树不为空
    {
        rear=1; //初始化
        front=0;
        queue[rear]=p;
        while(front<rear)//判断队列是否为空
        {
            front++;
            s=queue[front];
            if(s->key!=-1)
                count++;
            printf("key=%d color=%d\n",s->key,s->color);

            if(s->lchild!=NULL) //存储左右子节点
            {
                rear++;
                queue[rear]=s->lchild;
            }
            if(s->rchild!=NULL)
            {
                rear++;
                queue[rear]=s->rchild;
            }
            
            if(count>=n)
                break;
        }
    }
}


/*************************************************\
函数功能：查找一个节点在中序遍列中的下一个节点(后继)
输入：    一个节点、哨兵
输出：    该节点的后继节点
\*************************************************/
 RBTree* TreeNext(RBTree* node,RBTree* NIL) 
 {
        RBTree* result;
        if (node->rchild!=NIL) 
        {
            result = TreeMin(node->rchild,NIL);
        }
        else 
        {
            result = node->p;
            RBTree* temp = node;
            while (result!=NIL&&temp==result->rchild) 
            {
                temp = result;
                result = result->p;
            }
        }
        return result;
  }

 
/*************************************************\
函数功能：一个节点在中序遍列中的前一个节点(前趋)
输入：    一个节点、哨兵
输出：    该节点的前趋节点
\*************************************************/
    RBTree* TreePre(RBTree* node,RBTree* NIL) 
    {
        RBTree* result;
        if (node->lchild !=NIL)
        {
            result = TreeMax(node->rchild,NIL);
        }
        else 
        {
            result = node->p;
            RBTree* temp = node;
            while (result != NIL && temp == result->lchild)
            {
                temp = result;
                result = result->p;
            }
        }
        return result;
    }

        
/*************************************************\
函数功能：找到子树中最大的节点
输入：    根节点、哨兵
输出：    子树中最大的节点
\*************************************************/
    RBTree* TreeMax(RBTree* root,RBTree* NIL)
    {
        RBTree* result = root;
        while (result->rchild !=NIL) 
        {
            result = result->rchild;
        }
        return result;
    }

    
/*************************************************\
函数功能：找到子树中最小的节点
输入：    根节点、哨兵
输出：    子树中最小的节点
\*************************************************/
    RBTree* TreeMin(RBTree* root,RBTree* NIL)
    {
        RBTree* result = root;
        while (result->lchild !=NIL) 
        {
            result = result->lchild;
        }
        return result;
    }

---

实验结果

最后给出运行结果的说明：在我电脑上的运行结果为：

运行结果：

（key为关键字，color=0表示为红色，color=1表示为黑色，key=-1代表空节点）

插入节点的关键值为11
插入修正前的广度遍历:
key=11 color=0
key=-1 color=1
key=-1 color=1
插入修正后的广度遍历:
key=11 color=1
key=-1 color=1
key=-1 color=1

插入节点的关键值为2
插入修正前的广度遍历:
key=11 color=1
key=2 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
插入修正后的广度遍历:
key=11 color=1
key=2 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1

插入节点的关键值为14
插入修正前的广度遍历:
key=11 color=1
key=2 color=0
key=14 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
插入修正后的广度遍历:
key=11 color=1
key=2 color=0
key=14 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1

插入节点的关键值为1
插入修正前的广度遍历:
key=11 color=1
key=2 color=0
key=14 color=0
key=1 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
插入修正后的广度遍历:
key=11 color=1
key=2 color=1
key=14 color=1
key=1 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1

插入节点的关键值为7
插入修正前的广度遍历:
key=11 color=1
key=2 color=1
key=14 color=1
key=1 color=0
key=7 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
插入修正后的广度遍历:
key=11 color=1
key=2 color=1
key=14 color=1
key=1 color=0
key=7 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1

插入节点的关键值为15
插入修正前的广度遍历:
key=11 color=1
key=2 color=1
key=14 color=1
key=1 color=0
key=7 color=0
key=-1 color=1
key=15 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
插入修正后的广度遍历:
key=11 color=1
key=2 color=1
key=14 color=1
key=1 color=0
key=7 color=0
key=-1 color=1
key=15 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1

插入节点的关键值为5
插入修正前的广度遍历:
key=11 color=1
key=2 color=1
key=14 color=1
key=1 color=0
key=7 color=0
key=-1 color=1
key=15 color=0
key=-1 color=1
key=-1 color=1
key=5 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
插入修正后的广度遍历:
key=11 color=1
key=2 color=0
key=14 color=1
key=1 color=1
key=7 color=1
key=-1 color=1
key=15 color=0
key=-1 color=1
key=-1 color=1
key=5 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1

插入节点的关键值为8
插入修正前的广度遍历:
key=11 color=1
key=2 color=0
key=14 color=1
key=1 color=1
key=7 color=1
key=-1 color=1
key=15 color=0
key=-1 color=1
key=-1 color=1
key=5 color=0
key=8 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
插入修正后的广度遍历:
key=11 color=1
key=2 color=0
key=14 color=1
key=1 color=1
key=7 color=1
key=-1 color=1
key=15 color=0
key=-1 color=1
key=-1 color=1
key=5 color=0
key=8 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1

插入节点的关键值为4
插入修正前的广度遍历:
key=11 color=1
key=2 color=0
key=14 color=1
key=1 color=1
key=7 color=1
key=-1 color=1
key=15 color=0
key=-1 color=1
key=-1 color=1
key=5 color=0
key=8 color=0
key=-1 color=1
key=-1 color=1
key=4 color=0
插入修正后的广度遍历:
key=7 color=1
key=2 color=0
key=11 color=0
key=1 color=1
key=5 color=1
key=8 color=1
key=14 color=1
key=-1 color=1
key=-1 color=1
key=4 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=15 color=0

插入操作完成！！

形成的红黑树为：

删除节点的关键值为5

删除顶节点后的广度遍历：
key=7 color=1
key=2 color=0
key=11 color=0
key=1 color=1
key=4 color=1
key=8 color=1
key=14 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=15 color=0
请按任意键继续. . .

删除节点5后的红黑树为：

本文参考资料：《算法导论》